Regular expression search operations are employed in various applications including, for example, intrusion detection systems (IDS), virus protections, policy-based routing functions, Internet and text search operations, document comparisons, and so on. A regular expression can simply be a word, a phrase or a string of characters. For example, a regular expression including the string “gauss” would match data containing gauss, gaussian, degauss, etc. More complex regular expressions include metacharacters that provide certain rules for performing the match. Some common metacharacters are the wildcard “.”, the alternation symbol “|’, and the character class symbol “[ ].” Regular expressions can also include quantifiers such as “*” to match 0 or more times, “+” to match 1 or more times, “?” to match 0 or 1 times, {n} to match exactly n times, {n,} to match at least n times, and {n,m} to match at least n times but no more than m times. For example, the regular expression “a.{2}b” will match any input string that includes the character “a” followed exactly 2 instances of any character followed by the character “b.” Matching input strings for the regular expression “a.{2}b” include, for example, the input strings “abbb,” adgb,” “a7yb,” and “aaab.”
Traditionally, regular expression searches have been performed using software programs executed by one or more processors, for example, associated with a network search engine. However, as both the number and complexity of regular expressions increase for applications such as intrusion detection systems using access control lists, software solutions are less able to achieve desired search speeds and throughput. As a result, hardware solutions such as ternary content addressable memory (TCAM) based search engines are being developed that can implement and perform regular expression search operations at faster speeds than software solutions typically allow.
A typical CAM device includes a plurality of rows of CAM cells, each for storing a single data word. During compare operations, a search key is provided to the CAM device and is simultaneously compared with all the words stored therein to determine whether there is a match condition. If there are one or more matches, a priority encoder generates the index of the highest priority matching entry. Because the CAM entries are searched in parallel, search speed is not dependent upon the number of words stored in the CAM device. However, because the rows of a traditional CAM device cannot be connected together, the length of the data words stored therein is typically limited by the number of CAM cells in each row.
U.S. Pat. No. 6,252,789 discloses an inter-row configurable CAM device that includes a word expansion logic (WEL) circuit in each row of CAM cells. The WEL controls whether one or more consecutive rows of CAM cells are sequentially connected in a chain to form a data word chain that spans across multiple rows of the CAM array. More specifically, the WELs in all CAM rows that store the data words of the chain are configured to logically combine (e.g., AND) the match signals of the current CAM row and the previous adjacent CAM row and to forward the combined match signals to the next adjacent CAM row, and the WEL in the CAM row that stores the last data word outputs the match signals to the priority encoder. In this manner, the CAM device of the '789 can be configured to perform string match operations on words having very large lengths.
Unfortunately, because match signals from a CAM row in the '789 patent can be routed to only one adjacent row at a time, regular expressions must be unrolled for storage in the CAM device of the '789 patent. For example, to store the regular expression REG1=“ab(cd|ef|gh)uv” in the '789 CAM device, the REG1 are first unrolled to generate all possible matching strings (S1=“abcduv,” S2=“abefuv,” and S3=“abghuv”), and then the individual strings must be stored separately as 3 data word chains in 3 corresponding sets of contiguous CAM rows. Thus, for example, if each CAM row includes 8 CAM cells to store an 8-bit ASCII encoded character, then a first set of 6 contiguous CAM rows of the '789 patent are required to store S1=“abcduv,” a second set of 6 contiguous CAM rows are required to store S2=“abefuv,” and a third set of 6 contiguous CAM rows are required to store S3=“abghuv,” thereby requiring 18 contiguous rows in the '789 patent to store a regular expression that, in its original (e.g., rolled) form, includes only 10 characters.
The above-referenced co-pending and commonly owned U.S. patent application Ser. No. 12/131,922 (hereinafter referred to as the '922 application) discloses a TCAM-based search engine that can not only store regular expressions in their original or rolled form but also store complex regular expressions having various metacharacters, quantifiers, and/or character classes. More specifically, the TCAM device disclosed in the '922 application includes an array containing a plurality of rows of CAM cells each selectively connected to a programmable interconnect structure (PRS) that can be configured to selectively route the match signal from each CAM row as an input match signal to itself and/or to any number of other arbitrary selected CAM rows at the same time. The TCAM device also includes a number of counter circuits that can be selectively coupled to each other and/or to any number of the CAM rows by the PRS, which can be programmed to selectively route match signals from one or more CAM rows to the inputs of the counter circuits and to route the counter output signals as input match signals to one or more arbitrary selected CAM rows at the same time.
Row redundancy has been used to improve the yield of CAM devices. For example, U.S. Pat. No. 6,249,467 discloses a CAM device having a main array of CAM rows and a separate spare CAM row that can be selected to functionally replace a defective CAM row in the main CAM array by disabling the defective CAM row, enabling the spare CAM row, and mapping the address of the disabled defective CAM row to the enabled spare CAM row. However, because the spare CAM row is typically positioned below the main CAM array and is mapped directly to the disabled defective CAM row in the main array, the prior row redundancy technique disclosed in the '467 patent is not well suited for the PRS-equipped CAM device disclosed in the '922 application.
More specifically, because the CAM rows of the PRS-equipped CAM device are selectively interconnected by the PRS to form a match signal routing pattern that embodies the metacharacters and/or quantifiers of regular expressions to be stored therein, functionally replacing a defective CAM row with a spare CAM row using the prior row redundancy disclosed in the '467 patent requires re-routing the match signal connections associated with the defective CAM row to the spare CAM row using the PRS, which may not have sufficient resources for re-routing the match signal connections if the defective CAM row is not adjacent to the spare CAM row. For example, if there are a number I of intermediate CAM rows positioned between the defective CAM row and the spare CAM row, then functionally replacing the defective CAM row with the spare CAM row using such prior row redundancy techniques involves allocating PRS routing resources to re-route the match signal connections associated with the defective CAM row across the number I of intermediate CAM rows to the spare CAM row, which in turn reduces the amount of PRS resources available to implement the regular expressions.
Thus, to ensure that any defective CAM row in the array can be functionally replaced by the spare CAM row using techniques of the type described in the '467 patent, the PRS would need long signal lines extending across the entire array and the spare row (e.g., global PRS signal lines) and dedicated for row replacement operations. Unfortunately, providing global PRS signal lines dedicated for row redundancy consumes valuable circuit area that could otherwise be used to implement the signal routing pattern (e.g., between non-defective CAM rows) that embodies the regular expressions to be stored therein. Further, global PRS signal lines extending across the array that enable the match signal connections associated with any CAM row to be re-routed to the spare CAM row would have large parasitic capacitances (e.g., as compared to shorter PRS routing lines that extend across only several CAM rows), which degrades performance.
Thus, there is a need for a row redundancy scheme for a PRS-equipped CAM device that does not require dedicated PRS signal lines that extend between the spare CAM row and all main CAM rows of the array.
Like reference numerals refer to corresponding parts throughout the drawing figures.